.gif){kind=link}
Thực đơn
Số nguyên tố
Trong một thời gian dài, lý thuyết số nói chung và ngành nghiên cứu số nguyên tố nói riêng từng được xem là ví dụ kinh điển về toán học thuần túy khi không có ứng dụng nào ngoài phạm vi toán học,[lower-alpha 2] ngoại trừ việc dùng các bánh răng với số răng là số nguyên tố để hạn chế mài mòn.[117] Thậm chí, một số nhà lý thuyết số như nhà toán học người Anh G. H. Hardy còn tự hào về chính họ khi làm những công trình nghiên cứu hoàn toàn không có ý nghĩa quân sự gì.[118]
Góc nhìn này đã bị xóa bỏ vào những năm 1970, khi số nguyên tố đã có thể được dùng làm cơ sở để tạo ra các thuật toán mật mã hóa khóa công khai.[32] Những ứng dụng này đã góp phần đẩy mạnh hoạt động nghiên cứu thuật toán thực hiện phép tính trên số nguyên tố và các phương pháp kiểm tra tính nguyên tố của một số. Thuật toán kiểm tra tính nguyên tố cơ bản nhất, giải thuật chia thử, quá chậm đối với số rất lớn. Một nhóm thuật toán hiện đại có thể áp dụng được cho một số bất kỳ, trong khi còn có các thuật toán hiệu quả hơn dành cho các nhóm số đặc biệt. Đa số thuật toán kiểm tra tính nguyên tố chỉ cho biết đầu vào của chúng có phải là số nguyên tố hay không. Một số đoạn chương trình khác còn xuất ra một (hoặc tất cả) thừa số nguyên tố từ đầu vào là hợp số và được gọi là thuật toán phân tích số nguyên. Số nguyên tố cũng có ứng dụng trong điện toán như giá trị tổng kiểm, bảng băm và bộ sinh số giả ngẫu nhiên.
Phương pháp đơn giản nhất để kiểm tra tính nguyên tố của một số nguyên n {\displaystyle n} cho trước được gọi là giải thuật chia thử. Thuật toán này chia n {\displaystyle n} cho tất cả số nguyên từ 2 đến căn bậc hai của n {\displaystyle n} . Khi có bất kỳ số nguyên nào chia hết n {\displaystyle n} thì n {\displaystyle n} là hợp số, ngược lại thì nó là số nguyên tố. Các số lớn hơn căn bậc hai đó không cần được kiểm tra, vì khi n = a ⋅ b {\displaystyle n=a\cdot b} thì một trong hai thừa số a {\displaystyle a} và b {\displaystyle b} nhỏ hơn hoặc bằng căn bậc hai của n {\displaystyle n} . Một dạng tối ưu khác là chỉ kiểm tra các thừa số nguyên tố trong khoảng đó.[119] Chẳng hạn, để kiểm tra xem 37 có phải là số nguyên tố hay không, thuật toán này chia nó cho các số nguyên tố trong khoảng từ 2 đến √37, đó là số 2, 3 và 5. Cả ba phép chia đều có số dư khác 0 nên 37 chính là số nguyên tố.
Phương pháp này dù đơn giản nhưng nó không thực tế khi kiểm tra tính nguyên tố của các số nguyên lớn, vì số phép chia tăng dần theo cấp số nhân khi số chữ số của số nguyên đó càng nhiều.[120] Tuy nhiên, giải thuật chia thử vẫn được sử dụng để tìm nhanh hợp số với thừa số nhỏ trước khi áp dụng những phương pháp phức tạp hơn đối với các số vượt qua được giải thuật đó.[121]
Trước khi máy tính ra đời, nhiều bảng số liệt kê tất cả số nguyên tố hoặc phân tích nguyên tố đến một giới hạn cho trước đã được phát hành rộng rãi.[122] Phương pháp cổ xưa nhất để lập danh sách số nguyên tố được gọi là sàng Eratosthenes.[123] Hình minh họa bên phải cho thấy một dạng tối ưu của phương pháp này.[124] Một sàng khác hiệu quả hơn để giải quyết bài toán đó là sàng Atkin.[125] Trong toán học nâng cao, lý thuyết sàng áp dụng các phương pháp tương tự vào nhiều bài toán khác.[126]
Một số thuật toán hiện đại nhanh nhất để giải quyết bài toán về tính nguyên tố của một số n {\displaystyle n} bất kỳ cho trước là các thuật toán xác suất (Monte Carlo), nghĩa là nó có một khả năng nhỏ ngẫu nhiên cho câu trả lời sai.[127] Chẳng hạn, kiểm tra Solovay–Strassen với một số cho trước p {\displaystyle p} chọn ngẫu nhiên một số a {\displaystyle a} trong khoảng từ 2 đến p − 2 {\displaystyle p-2} và sử dụng lũy thừa mô đun để kiểm tra xem a ( p − 1 ) / 2 ± 1 {\displaystyle a^{(p-1)/2}\pm 1} có chia hết được bởi p {\displaystyle p} hay không.[lower-alpha 3] Nếu đúng là như vậy thì nó trả lời "có" và ngược lại thì nó trả lời "không". Nếu p {\displaystyle p} đúng là số nguyên tố thì nó luôn trả lời "có", nhưng nếu p {\displaystyle p} là hợp số thì nó trả lời "có" với xác suất lớn nhất là 1/2 và "không" với xác suất nhỏ nhất là 1/2.[128] Nếu thuật toán này được lặp lại n {\displaystyle n} lần trong cùng một số, xác suất lớn nhất để một hợp số vượt qua được thuật toán mọi lần là 1 / 2 n {\displaystyle 1/2^{n}} . Vì xác suất đó giảm dần theo cấp số nhân khi số lần thực hiện kiểm tra tăng dần nên nó dẫn đến khả năng cao (nhưng không chắc chắn) rằng một số vượt qua được thuật toán lặp lại đó là số nguyên tố. Mặt khác, nếu một số không vượt qua được kiểm tra thì nó chắc chắn là hợp số.[129] Một hợp số vượt qua được một kiểm tra như thế được gọi là số giả nguyên tố.[128]
Ngược lại, một số thuật toán khác đảm bảo rằng câu trả lời luôn luôn đúng: số nguyên tố sẽ luôn luôn được xác định là số nguyên tố và hợp số sẽ luôn luôn được xác định là hợp số. Chẳng hạn, phát biểu này là đúng đối với giải thuật chia thử. Những thuật toán với đầu ra đảm bảo chính xác bao gồm thuật toán tất định như phép kiểm tra tính nguyên tố AKS,[130] và các thuật toán Las Vegas ngẫu nhiên mà trong đó những lựa chọn ngẫu nhiên của thuật toán không ảnh hưởng gì đến kết quả cuối cùng, chẳng hạn như một số dạng của phép chứng minh tính nguyên tố bằng đường cong elliptic.[127] Khi phương pháp đường cong elliptic kết luận rằng một số là số nguyên tố, nó cũng xuất ra một chứng nhận tính nguyên tố có thể được xác nhận nhanh chóng.[131] Kỹ thuật đường cong elliptic là nhanh nhất trong số các thuật toán với độ chính xác tuyệt đối, nhưng thời gian thực thi chỉ được đo dựa trên thực nghiệm thay vì lập luận chứng minh. Kiểm tra AKS có độ phức tạp tính toán được chứng minh bằng lập luận toán học nhưng hoạt động chậm hơn so với kỹ thuật đường cong elliptic.[132] Các phương pháp này có thể được dùng để tạo ra các số nguyên tố lớn bằng cách tạo và kiểm tra các số ngẫu nhiên đến khi tìm được một số nguyên tố; khi đó, một thuật toán kiểm tra xác suất có thể nhanh chóng loại đi phần lớn hợp số trước khi một thuật toán "chắc chắn đúng" được dùng để xác thực lại rằng các số còn lại là số nguyên tố.[lower-alpha 4]
Bảng dưới đây liệt kê một số thuật toán như vậy. Thời gian hoạt động được cho theo số được kiểm tra n {\displaystyle n} và số vòng lặp k {\displaystyle k} (đối với thuật toán xác suất). Đồng thời, ε {\displaystyle \varepsilon } là một số dương nhỏ bất kỳ và log {\displaystyle \log } là logarit cơ số không xác định. Ký hiệu O lớn nghĩa là mỗi khoảng thời gian phải được nhân lên bởi một hằng số tỉ lệ để chuyển nó từ một đại lượng vô hướng sang đơn vị thời gian; hằng số này phụ thuộc vào thông số kỹ thuật chẳng hạn như loại máy tính được dùng để thực hiện thuật toán, nhưng không phụ thuộc vào tham số đầu vào n {\displaystyle n} và k {\displaystyle k} .
| Thuật toán | Năm phát triển | Dạng | Độ phức tạp thời gian | Ghi chú | Chú thích |
|---|---|---|---|---|---|
| Kiểm tra AKS | 2002 | tất định | O ( ( log n ) 6 + ε ) {\displaystyle O((\log n)^{6+\varepsilon })} | [130][133] | |
| Chứng minh đường cong elliptic | 1986 | Las Vegas | O ( ( log n ) 4 + ε ) {\displaystyle O((\log n)^{4+\varepsilon })} (theo thực nghiệm) | [132] | |
| Kiểm tra Baillie–PSW | 1980 | Monte Carlo | O ( ( log n ) 2 + ε ) {\displaystyle O((\log n)^{2+\varepsilon })} | [134][135] | |
| Kiểm tra Miller–Rabin | 1980 | Monte Carlo | O ( k ( log n ) 2 + ε ) {\displaystyle O(k(\log n)^{2+\varepsilon })} | xác suất sai số 4 − k {\displaystyle 4^{-k}} | [136] |
| Kiểm tra Solovay–Strassen | 1977 | Monte Carlo | O ( k ( log n ) 2 + ε ) {\displaystyle O(k(\log n)^{2+\varepsilon })} | xác suất sai số 2 − k {\displaystyle 2^{-k}} | [136] |
Cùng với các thuật toán nói trên áp dụng được cho bất kỳ số tự nhiên nào, một vài số với dạng đặc biệt còn có thể được kiểm tra tính nguyên tố nhanh hơn. Ví dụ, kiểm tra Lucas–Lehmer có thể xác định được một số Mersenne (lũy thừa của 2 trừ 1) có phải là số nguyên tố hay không một cách tất định với thời gian bằng với một vòng lặp của kiểm tra Miller–Rabin.[137] Đó là lý do kể từ năm 1992 (tính đến tháng 12 năm 2018) số nguyên tố lớn nhất đã biết luôn là một số nguyên tố Mersenne.[138] Có giả thuyết cho rằng có vô số số nguyên tố Mersenne.[139]
Bảng dưới đây liệt kê các số nguyên tố lớn nhất đã biết theo nhiều dạng khác nhau. Một vài trong số đó được tìm thấy qua điện toán phân tán. Năm 2009, dự án Great Internet Mersenne Prime Search đã được trao giải thưởng 100.000 đô la Mỹ cho số nguyên tố đầu tiên có ít nhất 10 triệu chữ số thập phân.[140] Tổ chức Biên giới Điện tử cũng có giải thưởng lần lượt là 150.000 và 250.000 đô la dành cho số nguyên tố có ít nhất 100 triệu và 1 tỷ chữ số.[141]
| Dạng số nguyên tố | Số nguyên tố | Số chữ số | Thời gian | Tìm ra bởi |
|---|---|---|---|---|
| Mersenne | 282.589.933 − 1 | 24.862.048 | 7 tháng 12 năm 2018[142] | Patrick Laroche, Great Internet Mersenne Prime Search |
| Proth | 10.223 × 231.172.165 + 1 | 9.383.761 | 31 tháng 10 năm 2016[143] | Péter Szabolcs, PrimeGrid[1] |
| Giai thừa | 208.003! − 1 | 1.015.843 | Tháng 7 năm 2016 | Sou Fukui[144] |
| Giai thừa nguyên tố[lower-alpha 5] | 1.098.133# − 1 | 476.311 | Tháng 3 năm 2012 | James P. Burt, PrimeGrid[145] |
| Sinh đôi | 2.996.863.034.895 × 21.290.000 ± 1 | 388.342 | Tháng 9 năm 2016 | Tom Greer, PrimeGrid[146] |
Cho một hợp số n {\displaystyle n} , công việc xuất ra một (hoặc tất cả) thừa số nguyên tố được gọi là phân tích của n {\displaystyle n} . Công việc này khó hơn đáng kể so với kiểm tra tính nguyên tố,[147] và mặc dù tồn tại nhiều thuật toán phân tích nhưng chúng đều chậm hơn so với các phương pháp nhanh nhất để kiểm tra tính nguyên tố. Giải thuật chia thử và thuật toán RHO có thể được dùng để tìm các nhân tử rất nhỏ của n {\displaystyle n} ,[121] và thuật toán phân tích bằng đường cong elliptic có thể hiệu quả khi n {\displaystyle n} có các nhân tử lớn vừa phải.[148] Một số phương pháp phù hợp đối với số lớn bất kỳ không phụ thuộc vào độ lớn của nhân tử bao gồm sàng cấp hai và sàng trường số thông thường. Giống như kiểm tra tính nguyên tố, có một số thuật toán phân tích yêu cầu đầu vào có dạng đặc biệt, trong đó có sàng trường số đặc biệt.[149] Tính đến tháng 2 năm 2020 số lớn nhất được phân tích bằng một thuật toán thông thường là RSA-250, một số có 250 chữ số (829 bit) và là tích của hai số nguyên tố lớn.[150]
Thuật toán Shor cho phép phân tích bất kỳ số nguyên nào với số bước đa thức trong một máy tính lượng tử.[151] Tuy nhiên, với công nghệ hiện nay thì thuật toán này chỉ hoạt động được với các số rất nhỏ. Tính đến tháng 10 năm 2012 số lớn nhất được phân tích bằng thuật toán Shor trong một máy tính lượng tử là 21.[152]
Một số thuật toán mật mã hóa khóa công khai, chẳng hạn như RSA và trao đổi khóa Diffie−Hellman được dựa trên số nguyên tố lớn (phổ biến nhất là số nguyên tố 2048 bit).[153] RSA dựa vào giả thiết rằng thực hiện phép nhân hai số lớn x {\displaystyle x} và y {\displaystyle y} dễ hơn nhiều so với khi tính x {\displaystyle x} và y {\displaystyle y} (giả sử là hai số nguyên tố cùng nhau) nếu chỉ biết một tích x y {\displaystyle xy} .[32] Trao đổi khóa Diffie−Hellman dựa vào thực tế rằng có một số thuật toán hiệu quả đối với lũy thừa mô đun (tính a b mod c {\displaystyle a^{b}{\bmod {c}}} ), trong khi phép tính ngược lại (logarit rời rạc) được cho là một bài toán khó.[154]
Số nguyên tố được sử dụng thường xuyên trong bảng băm. Chẳng hạn phương pháp ban đầu của Carter và Wegman đối với băm phổ quát được dựa vào việc tính hàm băm bằng cách chọn ngẫu nhiên hàm tuyến tính mô đun số nguyên tố lớn. Carter và Wegman đã khái quát hóa phương pháp này cho băm k {\displaystyle k} -độc lập bằng cách sử dụng đa thức bậc cao mô đun số nguyên tố lớn.[155] Cũng như trong hàm băm, số nguyên tố được dùng trong kích thước của bảng băm dựa trên dò cấp hai để đảm bảo rằng chuỗi dò bao phủ hết bảng đó.[156]
Một số phương pháp giá trị tổng kiểm được dựa trên kiến thức toán học về số nguyên tố. Chẳng hạn giá trị tổng kiểm dùng trong ISBN được xác định bằng cách lấy tổng của tất cả các chữ số (ngoài chữ số cuối cùng) mô đun 11. Vì 11 là số nguyên tố nên phương pháp này có thể phát hiện các chữ số bị sai và chuyển vị của các chữ số liền kề nhau.[157] Adler-32, một công cụ kiểm tra tổng kiểm khác, sử dụng số học mô đun 65521, số nguyên tố lớn nhất nhỏ hơn 2 16 {\displaystyle 2^{16}} .[158] Số nguyên tố cũng được dùng trong bộ sinh số giả ngẫu nhiên, trong đó có bộ sinh số đồng dư tuyến tính[159] và Mersenne Twister.[160]
Thực đơn
Số nguyên tốLiên quan
Tài liệu tham khảo
WikiPedia: Số nguyên tố